package com.company.modeldesign;

import java.util.LinkedList;

public class LRUCache {
    /*Lru 算法采用链表的形式 进行
    * head  --> node --> node --> .... --> tail -->null
    * 以tail 为最近使用的节点 每次找到对应节点后 进行尾部插入
    * 当到达容量限制后 采用 head 删除  删除的时间复杂度为 O(1)  采用尾删除 时间复杂度为 O(N)
    *
    *
    *
    * */
    private class Entity{
        int key;
        int value;

        public Entity(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private LinkedList<Entity> entities = new LinkedList<>();

    int cap = 10;
    public LRUCache(int capacity) {
        this.cap = capacity;
    }

    public int get(int key) {
        Entity target=null;
        for (Entity entity : entities) {
            if (entity.key == key) {
                target = entity;
                break;
            }
        }
        if (target == null) {
            return -1;
        }
        entities.remove(target);
        entities.addLast(target);
        if (entities.size()==cap+1) {
            entities.removeFirst();
        }
        return target.value;
    }

    public void put(int key, int value) {
        Entity target=null;
        for (Entity entity : entities) {
            if (entity.key==key) {
                entity.value = value;
                target = entity;
            }
        }
        if (target == null) {
            target = new Entity(key, value);
        }else {
            entities.remove(target);
        }
        entities.addLast(target);
        if (entities.size() == cap+1) {
            entities.removeFirst();
        }
    }


/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
}
